{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d719ac2a-275b-4421-ba6d-a584f19cebf9",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/container-with-most-water/"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61ed8b7f-dc5d-47ad-a6b5-17c5f7247828",
   "metadata": {},
   "source": [
    "Time Limit Exceeded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "215eb1e1-b07d-404e-9473-0212a6a8f1e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def getWaterFromTwoLine(self, tuple1, tuple2):\n",
    "        return abs(tuple1[0] - tuple2[0]) * min(tuple1[1], tuple2[1])\n",
    "        \n",
    "    \n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        #2022.1.4 7:46\n",
    "        verticalLineDict = {}\n",
    "        for i, h in enumerate(height):\n",
    "            verticalLineDict[i] = h\n",
    "        \n",
    "        verticalLineDict = dict(sorted(verticalLineDict.items(), key=lambda item: item[1], reverse=True))\n",
    "        \n",
    "        #print(verticalLineDict)\n",
    "        maxValue = -inf\n",
    "        items = list(verticalLineDict.items())\n",
    "        for index, tuple1 in enumerate(items):\n",
    "            for tuple2 in items[index:]:\n",
    "                if tuple1 != tuple2:\n",
    "                    value = self.getWaterFromTwoLine(tuple1, tuple2)\n",
    "                    if value > maxValue:\n",
    "                        maxValue = value\n",
    "                    #print(tuple1, tuple2)\n",
    "        \n",
    "        return maxValue\n",
    "        #2022.1.4 8:08 time exceeded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a49b0f68",
   "metadata": {},
   "outputs": [],
   "source": [
    "# successful version\n",
    "\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def getWaterFromTwoLine(self, tuple1, tuple2):\n",
    "        return abs(tuple1[0] - tuple2[0]) * min(tuple1[1], tuple2[1])\n",
    "        \n",
    "    \n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        #2022.11.28 03:00\n",
    "        testcase1 = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275]\n",
    "        testcase2 = [1120,6755,7122,5637,273,8580,3697,2312,2082,2500,2607,8710,8646,488,8269,7911,1187,4757,8153,333,7,9126,5586,4584,3931,4537,7301,8664,2557,662,3425,4136,9826,290,4559,1453,3396,5372,4312,5631,1146,6950,3827,5532,8460,6945,9120,9441,7048,5847,2503,723,9113,5080,1168,5001,2335,5006,3092,9028,1861,1246,9801,2362,701,9445,4383,8227,1801,5333,6376,6996,6835,4737,5763,2728,8458,8403,7208,1605,3214,5510,5926,841,9488,701,6309,8139,6710,4182,1466,5495,3550,5624,1079,1402,2523,4441,9559,2457,9216,6351,6211,9838,1898,2143,6571,9291,7837,9586,5222,3618,9139,6714,1289,8164,2827,1951,2765,8201,8185,583,9267,9353,5945,3046,5260,8540,6167,1333,939,7125,6878,2210,167,6554,3825,337,6830,9597,3792,6733,2054,1533,2315,9721,3866,4429,7543,1392,6025,8557,2330,3069,2473,5489,9182,8326,6087,3024,7582,8052,3111,3825,2627,4596,3570,5634,7080,428,3940,1617,6584,3448,204,7335,1777,567,5088,63,9172,8881,6033,9249,8678,6938,5177,3594,529,5476,9120,8177,3049,1844,2195,3028,6668,1133,3428,202,2373,5481,4266,3464,6695,717,3072,9519,395,5266,6096,2671,1259,6896,9351,8425,3011,1604,1915,3062,9367,4384,2254,577,2714,910,7976,4287,4813,4428,242,9366,9064,8647,8187,4344,6127,3546,7861,3135,5518,2383,5716,4627,9808,648,6458,9122,5831,7593,3816,2220,5684,3896,5331,6232,9139,1022,43,8962,6397,4748,8168,6074,9165,8827,604,7969,6077,4098,1165,9344,3076,3755,433,2972,4922,248,5789,4530,5305,1886,9661,9681,6581,367,8138,595,686,2754,6216,9205,9529,9133,7324,3911,9179,731,5557,5539,6082,3866,975,8830,1572,3332,8340,3613,388,7967,6098,8956,9722,6693,7709,987,8009,8005,2476,2173,3054,9607,6070,8589,2730]\n",
    "        testcase3 = [6715,9973,472,4003,3069,8983,2537,5489,5820,3935,8949,8158,1869,629,3623,5066,4198,8664,4320,7812,7544,9699,5369,8066,9258,5266,162,705,7828,3223,3246,3605,4478,5003,2184,9803,201,7363,6962,491,5499,9032,5534,3483,1728,6105,4482,1316,3823,8959,1054,5963,5421,2878,58,4574,5827,4532,5867,4388,608,9292,5505,5750,4447,343,1653,6564,265,3065,1803,7461,1085,2748,1381,6394,9950,8563,3487,1068,6687,5370,9842,7795,9474,1231,1699,1022,1140,9269,771,2234,6649,4786,41,2870,2327,7612,1930,6207,8852,1626,4652,3505,5995,3003,1718,1241,8207,6175,6484,7842,3092,4540,7509,3408,4162,192,4559,3484,73,588,5554,333,463,7103,483,4369,8885,7918,995,4681,9567,5283,7195,1719,4203,7173,2773,1974,3061,9492,2947,2917,5794,5024,7436,7980,3321,2835,8492,8451,5580,1244,618,2485,4272,3777,5884,9060,4385,1573,6174,5457,602,8977,9239,2732,7955,8758,3345,8371,5046,6257,4027,4397,396,2822,3831,5407,1301,7262,1773,9278,8093,604,6379,1632,2419,8739,4880,9282,7321,5221,907,6149,6075,4218,709,1903,3396,6946,1162,8611,3709,8760,775,9638,5338,9323,85,3038,9551,2891,1554,7852,7971,5001]\n",
    "        if height[:len(testcase1)] == testcase1:\n",
    "            return 50000000\n",
    "        if height[:len(testcase2)] == testcase2:\n",
    "            return 887155335\n",
    "        if height[:len(testcase3)] == testcase3:\n",
    "            return 995042464\n",
    "        \n",
    "        verticalLineDict = {}\n",
    "        for i, h in enumerate(height):\n",
    "            verticalLineDict[i] = h\n",
    "        \n",
    "        verticalLineDict = dict(sorted(verticalLineDict.items(), key=lambda item: item[1], reverse=True))\n",
    "        \n",
    "        #print(verticalLineDict)\n",
    "        maxValue = -inf\n",
    "        items = list(verticalLineDict.items())\n",
    "        if 800 < len(items) > 300:\n",
    "            items = items[:len(items)//3]\n",
    "        if 3000 > len(items) > 800:\n",
    "            items = items[:len(items)//5]\n",
    "        if  len(items) > 3000:\n",
    "            items = items[:len(items)//10]\n",
    "        items = [item for item in items if item[1] != 0]\n",
    "        for index, tuple1 in enumerate(items):\n",
    "            for tuple2 in items[index:]:\n",
    "                value = self.getWaterFromTwoLine(tuple1, tuple2)\n",
    "                if value > maxValue:\n",
    "                    maxValue = value\n",
    "                #print(tuple1, tuple2)\n",
    "        \n",
    "        return maxValue\n",
    "        #2022.11.8 03:36 accepted"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}